//
// Created by cheng on 2021/02/21.
// 计数排序
//

#include "../Utils/MyUtil.h"
#define MAX 12

using namespace std;

void CountingSort(vector<int>& a, vector<int>& b);

int main() {
    auto a = MyUtil::GetRandomIntVector(10, 0, MAX);
    MyUtil::PrintVector(a);
    vector<int> b = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    CountingSort(a, b);
    MyUtil::PrintVector(b);
}

void CountingSort(vector<int> &a, vector<int> &b) {
    auto tempArr = new int[MAX+1]{0};

    // 在tempArr[i]中记录i出现的次数
    for (auto item : a) {
        tempArr[item]++;
    }

    // 在tempArr中记录小于等于i的元素的出现位置
    for (int i = 1; i < MAX; i++) {
        tempArr[i] = tempArr[i] + tempArr[i-1];
    }

    MyUtil::PrintArray(tempArr, MAX);
    for (int i = a.size()-1; i > 0; i--) {
        b[tempArr[a[i]]] = a[i];
        tempArr[a[i]]--;
    }
    delete[] tempArr;
}
